package twice.class_digui;
//最长回文子序列
public class Class10_PalindromeSubsequence {
    public static int lpsl1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        return f(str, 0, str.length - 1);
    }
    public static int f(char[] str,int L,int R){
        if(L==R){
            return 1;
        }
        if(L==R-1){
            if(str[L] == str[R]){
                return 2;
            }
            else{
                return 1;
            }
        }
        int p1 = f(str,L+1,R-1);
        int p2 = f(str,L,R-1);
        int p3 = f(str,L+1,R);
        int p4 = str[L] != str[R] ? 0 : (2 + f(str, L + 1, R - 1));
        return Math.max(Math.max(p1,p2),Math.max(p3,p4));
    }
    public static int lpsl2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
       int[][] dp = new int[str.length][str.length];
       for(int i = 0; i < str.length;i++){
           dp[i][i] = 1;
       }
       for(int i = 0;i < str.length-1;i++){
           dp[i][i+1] = str[i] == str[i+1] ? 2 : 1;
       }
        for (int L = str.length - 3; L >= 0; L--) {
            for (int R = L + 2; R < str.length; R++) {
                dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
                if (str[L] == str[R]) {
                    dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
                }
            }
        }
        return dp[0][str.length-1];
    }
}
